package tree;

import org.w3c.dom.stylesheets.LinkStyle;

import java.util.*;

public class TreeDemo {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        Node root = new Node(0, "根节点");
    {
        tree.setRoot(root);
        Node node1 = new Node(1, "光头强");
        Node node2 = new Node(2, "喜洋洋");
        Node node3 = new Node(3, "美羊羊");
        Node node4 = new Node(4, "花洋洋");
        Node node5 = new Node(5, "慢羊羊");
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
    }
        List<Node> list = tree.sequentialStorageToarray(root);
        Node roottemp = tree.sequentialStorageTotree(list);
        tree.preTravel(roottemp);

    }
}
class BinaryTree{
    private Node root;
    private Node temp;

    public void setRoot(Node root) {
        this.root = root;
    }

    /**
     * 二叉树前序遍历
     */
    public void preTravel(Node temp){
        if (root==null){
            System.out.println("二叉树为空");
            return;
        }
        System.out.println(temp);
        if (temp.left!=null)
            preTravel(temp.left);
        if (temp.right!=null)
            preTravel(temp.right);
    }
    /**
     * 二叉树前序遍历的非递归实现
     */
    public void nonRecursionPreTravel(Node root){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        if (root!=null){
            //不是空树
            do{
                Node temp=stack.pop();
                System.out.println(temp);
                if ( temp.right!= null){
                    stack.push(temp.right);
                }
                if (temp.left!=null){
                    stack.push(temp.left);
                }
            }while(!stack.empty());
        }
    }
    /**
     * 二叉树中序遍历
     */
    public void midTravel(Node temp){
        if (root==null){
            System.out.println("二叉树为空");
            return;
        }
        if (temp.left!=null)
            midTravel(temp.left);
        System.out.println(temp);
        if (temp.right!=null)
           midTravel(temp.right);
    }
    /**
     * 二叉树后序遍历
     */
    public void afterTravel(Node temp){
        if (root==null){
            System.out.println("二叉树为空");
            return;
        }
        if (temp.left!=null)
           afterTravel(temp.left);
        if (temp.right!=null)
            afterTravel(temp.right);
        System.out.println(temp);
    }
    /**
     * 二叉树前序查找,用id查找姓名信息
     * @param id 要查找的id
     * @param temp 开始查找的节点,通常为根节点
     */
    public String preFind(int id,Node temp){
        if (root == null) {
            System.out.println("二叉树为空");
            return null;
        }
        if (temp.getId() == id) {
            return temp.getName();
        }
        String result = "查无此人";
        if (temp.left != null)
           result= preFind(id, temp.left);
        //左递归找到了
        if (!result.equals("查无此人")){
            return  result;
        }
        if (temp.right != null)
            return preFind(id, temp.right);
        //右递归找没找到,都得返回
        return result;
    }

    /**
     * 中序查找
     * @param id 欲查找的id
     * @param temp 开始查找的节点
     * @return id所对应的节点姓名
     */
    public String middleFind(int id,Node temp){
        if (root == null) {
            System.out.println("二叉树为空");
            return null;
        }

        String result = "查无此人";
        if (temp.left != null)
            result= middleFind(id, temp.left);

        if (temp.getId() == id) {
            return temp.getName();
        }
        //左递归找到了
        if (!result.equals("查无此人")){
            return  result;
        }
        if (temp.right != null)
            return middleFind(id, temp.right);
        //右递归找没找到,都得返回
        return result;
    }

    /**
     * 后序查找
     * @param id 欲查找的id
     * @param temp 开始查找的节点
     * @return id对应的姓名
     */
    public String afterFind(int id,Node temp){
        if (root == null) {
            System.out.println("二叉树为空");
            return null;
        }

        String result = "查无此人";

        if (temp.left != null)
            result= afterFind(id, temp.left);
        //左递归找到了
        if (!result.equals("查无此人")){
            return  result;
        }

        if (temp.right != null)
            result= afterFind(id, temp.right);
        //右递归找没找到
        if (!result.equals("查无此人")){
            return  result;
        }
        //对比当前节点
        if (temp.getId() == id) {
            return temp.getName();
        }
        return result;
    }

    /**
     * 为有序二叉树添加节点
     * @param newNode 新添加的节点
     *
     */
    public void insertNode(Node newNode){
        temp=root;
    }
    /**
     * 级联删除节点(删除某个节点时,将其子节点一并删除)
     * @param id 欲删除的节点id
     */
    public void delCaseCade(int id){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        if (root!=null){
            //不是空树
            do{
                Node temp=stack.pop();
                //删除判断
                if (temp.left.getId()==id){
                    temp.left=null;
                    break;
                }
                if(temp.right.getId()==id){
                    temp.right=null;
                    break;
                }
                if ( temp.right!= null){
                    stack.push(temp.right);
                }
                if (temp.left!=null){
                    stack.push(temp.left);
                }
            }while(!stack.empty());
        }
    }
    /**
     * 顺序存储二叉树,也就是将二叉树(完全二叉树)装进数组,(数组和二叉树)下标都从零开始,
     * 一层一层将二叉树装进数组类似于广度优先遍历
     */
    public List<Node> sequentialStorageToarray(Node root){
        //将root节点所带领的二叉树存进数组
        ArrayList<Node> seqList = new ArrayList<>();
        ArrayDeque<Node> queue = new ArrayDeque<>();

        queue.add(root);

        do {
            Node temp = queue.remove();
            seqList.add(temp);
            if (temp.left!=null)
                queue.add(temp.left);
            if (temp.right!=null)
                queue.add(temp.right);
        }while(!queue.isEmpty());


        return seqList;
    }
    /**
     * 顺序解析二叉树,也就是将数组转换成二叉树
     */
    public Node sequentialStorageTotree(List<Node> list){
        Node root =new Node(-1,"");

        //左节点是2n+1;右节点式2n+2
        for (int i=0;i<list.size();i++){
            temp=list.get(i);
            if (2*i+1>list.size()-1){
              temp.right=temp.right=null;
            }else if (2*i+1==list.size()-1){
               temp.left=list.get(2*i+1);
               temp.right=null;
            }else{
                temp.left=list.get(2*i+1);
                temp.right=list.get(i*2+2);
            }
        }

        return root;
    }
    /**
     * 线索化二叉树
     */
}
class Node{
    private int id;
    private String name;
    public Node left;
    public Node right;

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}
